package warm100;

import sun.reflect.generics.tree.Tree;
import utils.TreeNode;

/**
 * 手动创建一棵 26 叉树
 */
class Node {
    Node[] son = new Node[26];//无需存储节点值，孩子位序就代表了节点值
    boolean end;  //表示是否为某个字符串的终止节点。
}

public class Trie_208 {

    //树保存每个字母开头的前缀树
    private Node root;

    public Trie_208() {
        root = new Node();
        root.end = true;       //孩子都为null
    }

    //不用递归，类似链表
    public void insert(String word) {
        Node cur = root;
        for(char c : word.toCharArray()){  //需要插入所有字母
            if(cur.son[c-'a']==null)       //如果没有该字母，插入
                cur.son[c-'a'] = new Node();
            cur = cur.son[c-'a'];  //链表式遍历
        }
        cur.end = true;  //终点位置是某个字符串的终止节点
    }

    /**
     * 搜索是否存在字符串
     */
    public boolean search(String word) {
        return find( root, word.toCharArray())==1;
    }

    /**
     * 是否含有该前缀
     */
    public boolean startsWith(String prefix) {
        return find( root, prefix.toCharArray())!=0;    //1和2都代表找到了前缀
    }

    /**
     * @return    0 代表未找到 ，1 代表找到单词，2代表找到前缀
     */
    public int find(Node node, char[] chars) {
        Node cur = node;
        for(char c : chars){
            if(cur.son[c-'a']==null)
                return 0;         //未找到
            cur = cur.son[c-'a'];
        }
        return cur.end?1:2;    //是一个单词返回1，否则返回2
    }
}
